The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.
In searching geographic areas using airborne or land based mobile platforms, task allocation and path planning techniques are often employed in an attempt to utilize the resources at hand (i.e., the mobile platforms) most efficiently. However, many variables often exist that are not addressed with previously developed planning techniques. In many applications, particularly military applications, multiple mobile platforms, often both manned and unmanned, may be available for use in carrying out the search tasks. Additionally, different types of mobile platforms (airborne, land based, etc.) are available for use. Such mobile platforms may have widely varying capabilities and limitations. Furthermore, a search mission covering a predefined geographic region may require dealing with different visibility conditions (e.g., rain, fog, etc.) in different subregions of the predefined geographic region. The mobile platforms can have different capabilities and limitations, for example different operating speeds, turning radii, and different sensor foot prints (i.e., may carry sensors having different coverage area capabilities).
The vehicle conditions and capabilities also may change over time. Thus, a task allocation and path planning system and method is needed to adapt to varying vehicle conditions and capabilities. Environmental conditions such as visibility may also change over the search region over a given time period during which the searching mission is being carried out. Therefore, a need exists for a system and method that is able to detect and adapt to environmental changes in real time so that the assets available for the search are used in the optimum manner to efficiently carry out the searching activities in a minimum amount of time, and with a desired degree of confidence that a target present within any subregion will be detected. Such a system and method would most efficiently allocate the use of the available mobile platforms in a manner that minimizes the time and cost of finding targets within the various subregions of the predefined geographic region. Cost may be defined as the total time spent by all mobile platforms in order to visit every location within the predefined geographic region at least once, while achieving a guaranteed probability of target detection. As will also be appreciated, the overall complexity of searching a predefined geographic region can increase exponentially with the size and complexity of the region (shape, terrain, topography), as well as with the number of different vehicles being used and the variability in capabilities between vehicles, making the problem of allocating assets extremely difficult to solve. The addition of changing environmental and vehicle characteristics further complicates the problem with the need for adaptability. Examples of previous mission planning approaches include “GRAMMPS”, a generalized mission planner for multiple mobile robots, “ALLIANCE”, “MARTHA” and “MURDOCH”. The ALLIANCE mission planning architecture is a distributed, behavior-based mission planner utilizing ant colony optimization, where mobile platforms broadcast their current task and status, and free mobile platforms allocate themselves where there is the most need. The MARTHA method is a distributed, market based mission planner where mobile platforms place bids on available tasks representing the mobile platform's ability to achieve the task efficiently, with the task being allocated to the lowest bidder.
The above approaches, however, only address the problem of controlling multiple vehicles. None of these methods approach the search coverage problem, nor do they involve path planning for each vehicle. Furthermore, few of the above approaches deal with vehicles having widely varying capabilities. Essentially, these prior developed multi-robot task allocation approaches have been designed for predefined, discrete tasks, primarily with homogenous vehicles, and have approached adaptability by continuous re-planning. These methods would be highly computationally expensive if applied to the scenario of using heterogeneous mobile platforms under changing environmental conditions to search a predefined geographic region.